# -*- coding: utf-8 -*-
# @Time : 2021/3/19 11:11
# @Author : Jiangzhesheng
# @File : timetable_algo.py
# @Software: PyCharm
from typing import List
class TimeUnit:
    def __init__(self,start:int=None,end:int=None,weight=None) -> None:
        self.start=start
        self.end=end
        self.weight=weight

    def __repr__(self) -> str:
        return '%d--%d'%(self.start,self.end)

    @classmethod
    def tuple2Unit(cls,tuple:()):
        tmp=TimeUnit()
        tmp.start=tuple[0]
        tmp.end=tuple[1]
        try:
            tmp.weight=tuple[2]
        except IndexError:
            tmp.weight=0
        return tmp

class Reads(TimeUnit):
    def __init__(self, start, end) -> None:
        self.start=start
        self.end=end
        self.weight=end-start

    @classmethod
    def tuple2Unit(cls, tuple: ()):
        tmp=super().tuple2Unit(tuple)
        tmp.weight=tmp.end-tmp.start
        return tmp

def timetable_algo(time_list:List[TimeUnit])->List[TimeUnit]:
    """
    根据给定reads集合，挑出互不overlap的reads，对ref的覆盖度最大
    动态规划算法，排课问题
    :param time_list: 待挑选reads集，一个read由(start,end)表示，其weight=end-start
    :return:同上
    """
    # 首先根据end排序
    time_list.sort(key=lambda x:x.end)
    # 初始化dp数组
    pre,dp=[-1]*len(time_list),[0]*len(time_list)
    for i in range(len(time_list)):
        # 从当前read_i向前找第一个满足end[j]<=start[i]的read_j
        tmp=time_list[i].weight
        find_flag=False
        for j in range(i,-1,-1):
            if time_list[j].end<=time_list[i].start:
                tmp+=dp[j]
                find_flag=True
                break
        # dp[i]=max(dp[i-1],tmp)
        if dp[i-1]>tmp:
            dp[i]=dp[i-1]
            pre[i]=-1
        else:
            dp[i] = tmp
            pre[i]=j if find_flag else -2
    print('dp is',dp)
    print('pre is',pre)

    max_weight,choose=dp[-1],solve_pre(time_list,pre)

    return max_weight,choose

def solve_pre(time_list:List[TimeUnit],pre:List[int])->List[TimeUnit]:
    ans=[]
    i=len(pre)-1
    while True:
        cur=pre[i]
        if cur==-2:
            ans.insert(0,time_list[i])
            break
        elif cur==-1:
            i-=1
            continue
        else:
            ans.insert(0, time_list[i])
            i=cur
    return ans

def main():
    testcase=[(1,4),(3,5),(0,6),(5,7),(3,8),(5,9),(6,10),(8,11),(8,12),(2,13),(12,15)]
    print('running test with case:')
    print(testcase)
    l=[Reads.tuple2Unit(i) for i in testcase]
    max_weight,choose=timetable_algo(time_list=l)
    print('max_weight is',max_weight)
    print('choose unit:',choose)
if __name__ == '__main__':
    main()